package com.littrabble.matrix;

public class DynamicMatrixMM {

	public static void main(String[] args) {

		int[] d = {3, 2, 6, 7, 2, 2, 8};
		int n = d.length - 1;
		int[][] m = new int[n + 1][n + 1]; // i=0,j=0 不使用
		int[][] p = new int[n+1][n+1];

		/* initialize */
		for (int i = 1; i <= n; i++) {
			m[i][i] = 0;
		}

		for (int diagonal = 1; diagonal <= n - 1; diagonal++) {
			for (int i = 1; i <= n - diagonal; i++) {
				int j = i + diagonal;

				m[i][j] = Integer.MAX_VALUE;

				for (int k = i; k < j; k++) {
					int tmp = m[i][k] + m[k + 1][j] + d[i - 1] * d[k] * d[j];

					if (tmp < m[i][j]) {
						m[i][j] = tmp;
						p[i][j] = k;
					}
				}
			}
		}

		/* output */
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				System.out.printf("%5d", m[i][j]);
			}
			System.out.println();
		}
		
		/* output order */
		printOrder(p,1,n);
	}
	
	public static void printOrder(int[][] p,int i,int j) {
		if(i == j) {
			System.out.print("A" + i);
		} else {
			int k = p[i][j];
			System.out.print("(");
			printOrder(p,i,k);
			printOrder(p,k+1,j);
			System.out.print(")");
		}
	}
}
